package com.wfm.leetcode.editor.cn;

import com.wfm.common.ArrayUtils;
import java.util.Arrays;

public class POne88买卖股票的最佳时机IV{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2*k];
        for (int i = 0; i < k; i++) {
            dp[0][i*2] = -prices[0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j*2] = Math.max(dp[i-1][j*2],(j!=0?dp[i-1][j*2-1]:0)-prices[i]);
                dp[i][j*2+1] = Math.max(dp[i-1][j*2+1],dp[i-1][j*2]+prices[i]);
            }
        }
        ArrayUtils.printTwoNum(dp);
        return dp[n-1][2*k-1];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new POne88买卖股票的最佳时机IV().new Solution();
        System.out.println(solution.maxProfit(3, new int[]{1, 4, 1, 4, 1, 4}));
    }
}